package jjn.carl.dp;

import java.util.Scanner;

/**
 * @author Jiang Jining
 * @since 2023-08-21 0:02
 */
public class LeetCode377 {
    
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int i = 0; i <= target; i++) {
            for (int num : nums) {
                if (i >= num && dp[i] < Integer.MAX_VALUE - dp[i - num]) {
                    dp[i] += dp[i - num];
                }
            }
        }
        return dp[target];
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        int target = scanner.nextInt();
        int[] nums = new int[num];
        for (int i = 0; i < num; i++) {
            nums[i] = scanner.nextInt();
        }
        int combinationSum4 = new LeetCode377().combinationSum4(nums, target);
        System.out.println(combinationSum4);
    }
}
